"""
Problem 72: https://projecteuler.net/problem=72

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1,
it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we
get: 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7,
3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that there are 21 elements in this set.
How many elements would be contained in the set of reduced proper fractions for
d ≤ 1,000,000?
"""


# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/25
'''

import math

def reducedproperfraction(limit:int = 1000000) -> set:
    '''
    >>> print(len(reducedproperfraction(8)))
    21
    '''
    rpfSet = set()
    for p in range(1,limit):
        for q in range(p+1,limit+1):
            g = math.gcd(p,q)
            rpfSet.add((p//g,q//g))
    
    return rpfSet


def solution(limit: int = 1000000) -> int:
    return len(reducedproperfraction(limit))
    


def eulerPhi(limit:int = 1000000)->list:
    
    phi = [i - 1 for i in range(limit + 1)]
    # print(phi)

    for i in range(2, limit + 1):
        if phi[i] == i - 1:
            # input(f'{i}:{phi[i]}')
            for j in range(2 * i, limit + 1, i):
                # input(f'{j}:{phi[j]}, {phi[j]} <--- {phi[j]} - {phi[j]}/{i}')
                phi[j] -= phi[j] // i
                # print('-->',phi[j])
    
    return phi


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    #print(solution(1000))
    # 304191

    print(sum(eulerPhi()[2:]))
    # 303963552391
